/*
 * @lc app=leetcode.cn id=57 lang=golang
 *
 * [57] 插入区间
 */

// @lc code=start

// 中间插入、最前端插入、尾端插入
func insert(intervals [][]int, newInterval []int) [][]int {

	n := len(intervals)
	if n == 0 {
		return append(intervals, newInterval)
	}
	index := n
	for i := 0; i < n; i++ {
		if newInterval[0] < intervals[i][0] {
			index = i
			break
		}
	}

	res := make([][]int, index, n+1)
	copy(res, intervals)
	if index == 0 {
		res = append(res, newInterval)
	} else {
		if newInterval[0] > res[len(res)-1][1] {
			res = append(res, newInterval)
		} else {
			if newInterval[1] > res[len(res)-1][1] {
				res[len(res)-1][1] = newInterval[1]
			}

		}
	}

	// fmt.Println(res)
	for i := index; i < n; i++ {
		newInterval = intervals[i]
		if newInterval[0] > res[len(res)-1][1] {
			res = append(res, newInterval)
		} else {
			if newInterval[1] > res[len(res)-1][1] {
				res[len(res)-1][1] = newInterval[1]
			}

		}
	}
	return res
}

// @lc code=end
